package cn.nju.seg.atg.GA;

import java.util.ArrayList;
import java.util.Date;

/**
 *该类表示种群 - 模拟自然界生物进化机制，对种群进行遗传进化操作。
 */
public abstract class Population implements Runnable{
    /** 
     *种群进化最大迭代次数
     */
    int maxGenerations; 

    /** 
     * 预筛选的个体数量
     */
    int numPrelimRuns; 

    /** 
     * 筛选个体时的最大迭代次数，
     * 预筛选方法可以提供平均适应度较高的初始种群。
     */
    int maxPrelimGenerations; 

    /** 
     * 1-100 (e.g. 10 = 10% 随机选择的概率--不基于个体适应度). 
     * 可以提高种群进化的多样性。
     */ 
    int randomSelectionChance; 

    /** 
     *交叉概率
     */
    double crossoverProb; 
    
    /** 
     * 突变概率
     */
    double mutationProb; 
    
    /** 
     * 染色体中基因的个数
     */
    protected int chromosomeDim; 
    
    /** 
     * 种群中个体数量。
     * 一般情况下，更大的种群可以产生更好的进化结果，但将减慢进化速度。
      */
    protected int populationDim; 
    
    /** 
     * 当前种群
     */
    protected Chromosome[] chromosomes; 
    
    /** 
     * 下一代种群
     */
    Chromosome[] chromNextGen; 
    
    /** 
     * 预筛选种群
     */
    Chromosome[] prelimChrom; 
    
    /** 
     * 当前种群中最优个体在个体数组中的下标
     */
    int bestFitnessChromIndex; 
    
    /** 
     * 当前种群中最差个体在个体数组中的下标
     */
    int worstFitnessChromIndex; 
    
    /** 
     * 交叉方式
     */
    protected int crossoverType; 
    
    /** 
     * 数据统计--种群的平均偏差值。
     */
    double[] genAvgDeviation; 
    
    /** 
     * 数据统计--种群的平均适应度值。
     */
    double[] genAvgFitness; 
    
    /** 
     * 是否为每代种群进行数据统计。
     */ 
    boolean computeStatistics; 

    /** 
     * 为种群初始化，即为每个个体初始基因序列。
     */
    abstract protected void initPopulation();
    
    /** 
     * 变异操作
     */
    abstract protected void doRandomMutation(int iChromIndex);
    
    /**
     * 一点交叉
     */
    abstract protected void doOnePtCrossover(Chromosome Chrom1, Chromosome Chrom2);
    
    /**
     * 两点交叉
     */
    abstract protected void doTwoPtCrossover(Chromosome Chrom1, Chromosome Chrom2);
    
    /** 
     * 一致交叉
     */
    abstract protected void doUniformCrossover(Chromosome Chrom1, Chromosome Chrom2);
    
    /** 
     * 获取给定个体的适应度值
     */
    abstract protected double getFitness(int iChromIndex);
    
    /**
     * 种群进化
     */
    public void run(){
		evolve();

    }

    /**
     *初始化种群
     * @param chromosomeDim
     * @param populationDim
     * @param crossoverProb
     * @param randomSelectionChance
     * @param maxGenerations
     * @param numPrelimRuns
     * @param maxPrelimGenerations
     * @param mutationProb
     * @param crossoverType
     * @param computeStatistics
     */
    public Population(int chromosomeDim,
              int populationDim,
              double crossoverProb,
              int randomSelectionChance,
              int maxGenerations,
              int numPrelimRuns,
              int maxPrelimGenerations,
              double mutationProb,
              int crossoverType,
              boolean computeStatistics){
        this.randomSelectionChance = randomSelectionChance;
        this.crossoverType = crossoverType;
        this.chromosomeDim = chromosomeDim;
        this.populationDim = populationDim;
        this.computeStatistics = computeStatistics;

        this.chromosomes = new Chromosome[populationDim];
        this.chromNextGen = new Chromosome[populationDim];
        this.prelimChrom = new Chromosome[populationDim];
        this.genAvgDeviation = new double[maxGenerations];
        this.genAvgFitness = new double[maxGenerations];

        this.crossoverProb = crossoverProb;
        this.maxGenerations = maxGenerations;
        this.numPrelimRuns = numPrelimRuns;
        this.maxPrelimGenerations = maxPrelimGenerations;
        this.mutationProb = mutationProb;
    }

    /**
     * 获取指定某代种群的平均偏差值。
     * @param iGeneration
     * @return double
     */
    public double getAvgDeviation(int iGeneration){
        return (this.genAvgDeviation[iGeneration]);
    }

    /**
     * 获取指定某代种群的平均适应度值。
     * @param iGeneration
     * @return double
     */
    public double getAvgFitness(int iGeneration){
        return (this.genAvgFitness[iGeneration]);
    }

    /**
     * 获取种群进化最大迭代次数。
     * @return int
     */
    public int getMaxGenerations(){
        return maxGenerations;
    }

    /**
     * 获取需要预筛选的个体数目
     * @return int
     */
    public int getNumPrelimRuns(){
        return numPrelimRuns;
    }

    /**
     * 获取筛选个体时的种群进化最大迭代次数
     * @return int
     */
    public int getMaxPrelimGenerations(){
        return maxPrelimGenerations;
    }

    /**
     * 获取随机选择概率
     * @return int
     */
    public int getRandomSelectionChance(){
        return randomSelectionChance;
    }

    /**
     * 获取交叉概率 
     * @return double
     */
    public double getCrossoverProb(){
        return crossoverProb;
    }

    /**
     * 获取突变概率
     * @return double
     */
    public double getMutationProb(){
        return mutationProb;
    }
    
    /**
     * 获取染色中基因的个数
     * @return int
     */
    public int getChromosomeDim(){
        return chromosomeDim;
    }

    /**
     * 获取种群中个体数量
     * @return int
     */
    public int getPopulationDim(){
        return populationDim;
    }

    /**
     * 获取交叉方式
     * @return
     */
    public int getCrossoverType(){
        return crossoverType;
    }

    /**
     * 获取是否需要为每代种群进行数据统计的信息
     * @return boolean
     */
    public boolean getComputeStatistics(){
        return computeStatistics;
    }

    /**
     * 获取种群中最优个体
     * @return Chromosome
     */
    public Chromosome getFittestChromosome(){
        return (this.chromosomes[bestFitnessChromIndex]);
    }

    /**
     * 获取种群中最优个体的适应度值
     * @return double
     */
    public double getFittestChromosomesFitness(){
        return (this.chromosomes[bestFitnessChromIndex].fitness);
    }

    /**
     * 在0和给定的int型上界之间获取一个随机的int型数
     * @param upperBound
     * @return int
     */
    public int getRandom(int upperBound){
        int iRandom = (int) (Math.random() * upperBound);
        return (iRandom);
    }

    /**
     * 在0和给定的double型上界之间获取一个随机的double型数
     * @param upperBound
     * @return double
     */
    public double getRandom(double upperBound){
        double dRandom = (Math.random() * upperBound);
        return (dRandom);
    }

    /**
     * 种群进化操作
     * @return number of generations
     */
    public int evolve(){
        int iGen;
        int iPrelimChrom, iPrelimChromToUsePerRun;

        System.out.println("GA start time: " + new Date().toString());

        if (numPrelimRuns > 0){
            iPrelimChrom = 0;
            //number of fittest prelim chromosomes to use with final run
            iPrelimChromToUsePerRun = populationDim / numPrelimRuns;

            for (int iPrelimRuns = 1; iPrelimRuns <= numPrelimRuns; iPrelimRuns++){
                iGen = 0;
                initPopulation();

                //create a somewhat fit chromosome population for this prelim run
                while (iGen < maxPrelimGenerations){
                    //System.out.println(iPrelimRuns + " of " + numPrelimRuns + " prelim runs --> " +
                    //                 (iGen + 1) + " of " + maxPrelimGenerations + " generations");

                    computeFitnessRankings();
                    doGeneticMating();
                    copyNextGenToThisGen();

                    if (computeStatistics == true){
//                        this.genAvgDeviation[iGen] = getAvgDeviationAmongChroms();
                        this.genAvgFitness[iGen] = getAvgFitness();
                    }
                    iGen++;
                }

                computeFitnessRankings();

                //copy these somewhat fit chromosomes to the main chromosome pool
                int iNumPrelimSaved = 0;
                for (int i = 0; i < populationDim && iNumPrelimSaved < iPrelimChromToUsePerRun; i++)
                    if (this.chromosomes[i].fitnessRank >= populationDim - iPrelimChromToUsePerRun){
                        this.prelimChrom[iPrelimChrom + iNumPrelimSaved].copyChromGenes(this.chromosomes[i]);
                        //store these fit chromosomes
                        iNumPrelimSaved++;
                    }
                iPrelimChrom += iNumPrelimSaved;
            }
            for (int i = 0; i < iPrelimChrom; i++)
                this.chromosomes[i].copyChromGenes(this.prelimChrom[i]);
            System.out.println("INITIAL POPULATION AFTER PRELIM RUNS:");
        }
        else
            System.out.println("INITIAL POPULATION (NO PRELIM RUNS):");

        //Add Preliminary Chromosomes to list box
//        addChromosomesToLog(0, 10);

        iGen = 0;
        while (iGen < maxGenerations){
            computeFitnessRankings();
            if (computeStatistics == true){
//              this.genAvgDeviation[iGen] = getAvgDeviationAmongChroms();
                this.genAvgFitness[iGen] = getAvgFitness();
            }
            if(computeStatistics == true &&(Math.abs(this.chromosomes[bestFitnessChromIndex].fitness-genAvgFitness[iGen])<1)){         	
            	break;
            }
            
            iGen++;
            doGeneticMating();
            copyNextGenToThisGen();
        }

//       System.out.println("GEN " + (iGen + 1) + " AVG FITNESS = " + this.genAvgFitness[iGen-1] +
//                           " AVG DEV = " + this.genAvgDeviation[iGen-1]);

//        addChromosomesToLog(iGen, 10); 
        
        //display Chromosomes to system.out
        computeFitnessRankings();
		if(GA_for_ATG.isIntType == true){
			GA_for_ATG.mInputValue = new ArrayList<Long>();
		    for (int i=0; i<GA_for_ATG.NUM_OF_PARAM; i++){		       
		    	GA_for_ATG.mInputValue.add(new Long((long)(GA_for_ATG.LEFT_BOUNDARY + ((GA_for_ATG.RIGHT_BOUNDARY - GA_for_ATG.LEFT_BOUNDARY)/(Math.pow(2.0,GA_for_ATG.len)))*GA_for_ATG.getChromValAsArray(getFittestChromosome().getGenesAsStr())[i])));
		    }
		}
		else{
			GA_for_ATG.mInputValue2 = new ArrayList<Double>();
		    for (int i=0; i<GA_for_ATG.NUM_OF_PARAM; i++){		       
//		    	GA_for_ATG.mInputValue2.add(new Double((GA_for_ATG.LEFT_BOUNDARY + ((GA_for_ATG.RIGHT_BOUNDARY - GA_for_ATG.LEFT_BOUNDARY)/(Math.pow(2.0,GA_for_ATG.len)))*GA_for_ATG.getChromValAsArray(getFittestChromosome().getGenesAsStr())[i])));
		    	if(i == 0)
		    		GA_for_ATG.mInputValue2.add(new Double( (-15 + ((30)/(Math.pow(2.0,GA_for_ATG.len)))*GA_for_ATG.getChromValAsArray(getFittestChromosome().getGenesAsStr())[i])));
					if(i == 1){
						GA_for_ATG.mInputValue2.add(new Double((GA_for_ATG.LEFT_BOUNDARY + ((GA_for_ATG.RIGHT_BOUNDARY - GA_for_ATG.LEFT_BOUNDARY)/(Math.pow(2.0,GA_for_ATG.len)))*GA_for_ATG.getChromValAsArray(getFittestChromosome().getGenesAsStr())[i])));				 
					}
		    }
		}
//        System.out.println("Best Chromosome Found: ");
//        System.out.println(this.chromosomes[this.bestFitnessChromIndex].getGenesAsStr() +
//                           " fitness= " + this.chromosomes[this.bestFitnessChromIndex].fitness);

        System.out.println("GA end time: " + new Date().toString());
        return (iGen);
    }

    /**
     * 获取当前种群的平均适应度值
     * @return double
     */
    public double getAvgFitness(){
        double rSumFitness = 0.0;

        for (int i = 0; i < populationDim; i++)
            rSumFitness += this.chromosomes[i].fitness;
        return (rSumFitness / populationDim);
    }

    /**
     * 从种群中随机挑选两个个体。
     * 个体适应度值越高，被挑选的概率越大。
     * @param indexParents
     */
    public void selectTwoParents(int[] indexParents){
        int indexParent1 = indexParents[0];
        int indexParent2 = indexParents[1];
        boolean bFound = false;
        int index;

        while (bFound == false){
            index = getRandom(populationDim); 

            if (randomSelectionChance > getRandom(100)){
                indexParent1 = index;
                bFound = true;
            }
            else{
                //个体适应度等级越高，被挑选的概率越大
                if (this.chromosomes[index].fitnessRank + 1 > getRandom(populationDim)){
                    indexParent1 = index;
                    bFound = true;
                }
            }
        }

        bFound = false;
        while (bFound == false){
            index = getRandom(populationDim); 

            if (randomSelectionChance > getRandom(100)){
                if (index != indexParent1){
                    indexParent2 = index;
                    bFound = true;
                }
            }
            else{
                //个体适应度等级越高，被挑选的概率越大
                if ((index != indexParent1)
                    && (this.chromosomes[index].fitnessRank + 1 > getRandom(populationDim))){
                    //          if (this.chromosomes[index].getNumGenesInCommon(this.chromosomes[indexParent1])+1 > getRandom(chromosomeDim))
                    //          {
                    //            indexParent2 = index;
                    //            bFound = true;
                    //          }
                    indexParent2 = index;
                    bFound = true;
                }
            }
        }

        indexParents[0] = indexParent1;
        indexParents[1] = indexParent2;
    }

    /**
     * 根据个体适应度值计算个体的适应度等级。
     * 0表示等级最低，适应度值最小；popDim(种群中个体数量)表示等级最高，适应度值最大。
     * @param fitness
     * @return int the fitness ranking
     */
    private int getFitnessRank(double fitness){
        int fitnessRank = -1;
        for (int i = 0; i < populationDim; i++)
        {
            if (fitness >= this.chromosomes[i].fitness)
                fitnessRank++;
        }

        return (fitnessRank);
    }

    /**
     * 根据个体适应度值，为每个个体分配一个等级. 等级越高，个体的适应度值越高，即被遗传的概率越大。
     */
    private void computeFitnessRankings(){
        for (int i = 0; i < populationDim; i++){
            this.chromosomes[i].fitness = getFitness(i);
        }
        for (int j = 0; j < populationDim; j++)
            this.chromosomes[j].fitnessRank = getFitnessRank(this.chromosomes[j].fitness);

//      double rBestFitnessVal;
//      double rWorstFitnessVal;
        for (int j = 0; j < populationDim; j++){
            if (this.chromosomes[j].fitnessRank == populationDim - 1){
//              rBestFitnessVal = this.chromosomes[i].fitness;
                this.bestFitnessChromIndex = j;
            }
            if (this.chromosomes[j].fitnessRank == 0){
//              rWorstFitnessVal = this.chromosomes[i].fitness;
                this.worstFitnessChromIndex = j;
            }
        }
    }

    /**
     * 将当前种群通过交配产生更好的个体遗传到下一代。
     * 使用最优个体保留策略(最优的两个个体总是直接遗传到下一代)，
     * 这种方法可以使得最优个体在逐代进化间得以保留。
     */
    private void doGeneticMating(){
        int iCnt, iRandom;
        int indexParent1 = -1, indexParent2 = -1;
        Chromosome Chrom1, Chrom2;

        iCnt = 0;

        //适应度最优的个体直接拷贝到下一代(2个)
        this.chromNextGen[iCnt].copyChromGenes(this.chromosomes[this.bestFitnessChromIndex]);
        iCnt++;
   //     this.chromNextGen[iCnt].copyChromGenes(this.chromosomes[this.bestFitnessChromIndex]);
   //     iCnt++;

        if (this instanceof StringGA){
            Chrom1 = new CharsChromosome(chromosomeDim);
            Chrom2 = new CharsChromosome(chromosomeDim);
        }
        else //FloatGA
        {
            Chrom1 = new FloatChromosome(chromosomeDim);
            Chrom2 = new FloatChromosome(chromosomeDim);
        }

        do{
            int indexes[] = { indexParent1, indexParent2 };
            selectTwoParents(indexes);
            indexParent1 = indexes[0];
            indexParent2 = indexes[1];

            Chrom1.copyChromGenes(this.chromosomes[indexParent1]);
            Chrom2.copyChromGenes(this.chromosomes[indexParent2]);

            if (getRandom(1.0) < crossoverProb) {
            	//do crossover
                if (this.crossoverType == CrossoverModel.ctOnePoint)
                    doOnePtCrossover(Chrom1, Chrom2);
                else if (this.crossoverType == CrossoverModel.ctTwoPoint)
                    doTwoPtCrossover(Chrom1, Chrom2);
                else if (this.crossoverType == CrossoverModel.ctUniform)
                    doUniformCrossover(Chrom1, Chrom2);
                else if (this.crossoverType == CrossoverModel.ctRoulette){
                    iRandom = getRandom(3);
                    if (iRandom < 1)
                        doOnePtCrossover(Chrom1, Chrom2);
                    else if (iRandom < 2)
                        doTwoPtCrossover(Chrom1, Chrom2);
                    else
                        doUniformCrossover(Chrom1, Chrom2);
                }

                this.chromNextGen[iCnt].copyChromGenes(Chrom1);
                iCnt++;
                this.chromNextGen[iCnt].copyChromGenes(Chrom2);
                iCnt++;
            }
            else {
            	//如果不进行交叉操作，则将父染色体直接拷贝给子染色体。
                
            	// CREATE OFFSPRING ONE
                this.chromNextGen[iCnt].copyChromGenes(Chrom1);
                iCnt++;

                // CREATE OFFSPRING TWO
                this.chromNextGen[iCnt].copyChromGenes(Chrom2);
                iCnt++;
            }
        }
        while (iCnt < populationDim);
    }

    /**
     * 将前代种群拷贝到下一代。
     * 在恰当的时候对某些个体执行变异操作。
     */
    private void copyNextGenToThisGen(){
        for (int i = 0; i < populationDim; i++){
            this.chromosomes[i].copyChromGenes(this.chromNextGen[i]);

            //只有当个体不是最优个体时才执行变异操作
            if (i != this.bestFitnessChromIndex){
                //具有最低适应度的个体总要执行变异操作
                if ((i == this.worstFitnessChromIndex) || (getRandom(1.0) < mutationProb))
                    doRandomMutation(i);
            }
        }
    }

    /**
     *打印种群中某些个体
     * @param iGeneration
     * @param iNumChromosomesToDisplay
     */
    private void addChromosomesToLog(int iGeneration, int iNumChromosomesToDisplay){
        String sGen, sChrom;

        if (iNumChromosomesToDisplay > this.populationDim)
            iNumChromosomesToDisplay = this.populationDim;

        //打印个体串
        for (int i = 0; i < iNumChromosomesToDisplay; i++){
            this.chromosomes[i].fitness = getFitness(i);
            sGen = "" + iGeneration;
            if (sGen.length() < 2)
                sGen = sGen + " ";
            sChrom = "" + i;
            if (sChrom.length() < 2)
                sChrom = sChrom + " ";
            System.out.println("Gen " + sGen + ": Chrom" + sChrom + " = " + 
                               this.chromosomes[i].getGenesAsStr() + ", fitness = " + 
                               this.chromosomes[i].fitness);
            //System.out.print("this chromosome's true value:");
            //translateChromToParams(this.chromosomes[i].getGenesAsStr());
            //System.out.println("");
        }
    }

    /**
     * 获取当前种群的偏差值
     * 偏差值越小，种群的收敛程度越高。
     * 计算方式为：和最优个体相比，当前种群的所有个体中有多少基因位不同。
     * @return double
     */
    protected double getAvgDeviationAmongChroms(){
        int devCnt = 0;
        for (int iGene = 0; iGene < this.chromosomeDim; iGene++){
            if (this instanceof StringGA){
                char bestFitGene = ((CharsChromosome)this.chromosomes[this.bestFitnessChromIndex]).getGene(iGene);
                for (int i = 0; i < this.populationDim; i++){
                    char thisGene = ((CharsChromosome)this.chromosomes[i]).getGene(iGene);
                    if (thisGene != bestFitGene)
                        devCnt++;
                }
            }
            else {//FloatGA
                double bestFitGene =
                    ((FloatChromosome)this.chromosomes[this.bestFitnessChromIndex]).getGene(iGene);
                for (int i = 0; i < populationDim; i++)
                {
                    double thisGene = ((FloatChromosome)this.chromosomes[i]).getGene(iGene);
                    if (thisGene != bestFitGene)
                        devCnt++;
                }
            }
        }

        return ((double)devCnt);
    }

    /**
     * 将二进制串转换为long类型
     * @param sBinary
     * @return long
     */
    protected long binaryStrToInt(String sBinary){
        long digit, iResult = 0;

        int iLen = sBinary.length();
        for (int i = iLen - 1; i >= 0; i--){
            if (sBinary.charAt(i) == '1')
                digit = 1;
            else
                digit = 0;
            iResult += (digit << (iLen - i - 1));
        }
        return (iResult);
    }
   
}
